/* 单链表相关操作:

 链表最后添加结点;
 在index位置插入结点;
 删除指定位置的结点;
 判断一个链表是否是回文结构;
 单链表选择排序;
 单链表插入排序;
 单链表冒泡排序;
 单链表快速排序;
 合并两个有序链表;
 单链表归并排序;
 单链表反转;
 单链表部分反转;
 计算单链表的长度;
 获取倒数第k个结点;
 删除倒数第k个结点;
 删除第k个结点;
 删除链表中间节点;
 判断链表是否有环;
 删除单链表中值重复出现的结点;
 删除链表上值为n的结点;
 向有序环形链表中插入新结点;
 判断两个无环链表是否相交;
 遍历单链表，打印所有结点值
 */



public class SingleLinkedList{
	
	public Node head;
    
	//构造方法，定义头结点
    public SingleLinkedList(int data){
        this.head = new Node(data);
    }
	
    //内部结点类
	public class Node{
		public int value;
		public Node next;
		public Node(int data){
			this.value = data;
		}
	}
	
	//创建结点
	public Node createNode(int data){
	    Node node = new Node(data);
	    return node;
	}
	
    //链表最后添加结点
	public void addNode(Node node){
		Node temp = this.head;
		while(temp.next != null){
			temp=temp.next;
		}
		temp.next=node;
	}
	
	//在index位置插入结点，index=0为头结点
	public void insertNodeByIndex(int index,Node node){
		//判断输入的位置是否合法
		if(index<0){
			System.out.println("invalid index");
			return;
		}
		//插入位置在链表头结点
		if(index==0){
			node.next = this.head;
			this.head = node;
			return;
		}
		//将node插在temp后面，temp.next为当前位置
		Node temp =head; 
		int length = 1;
		while(temp.next!=null){
			if(index==length++){
				node.next = temp.next;
				temp.next = node;
				return;
			}
			temp=temp.next;	
		}
		System.out.println("invalid index");
	}
	
	//删除指定位置的结点
	public void delNodeByIndex(int index){
		if(index<0){
			System.out.println("invalid index");
			return;
		}
		if(index==0){
			this.head = this.head.next;
			return;
		}
		int length=1;
		Node temp = this.head;
		while(temp.next!=null){
			if(index==length++){
				temp.next = temp.next.next;
				return;
			}
			temp = temp.next;
		}
		System.out.println("invalid index");	
	}
	
	//判断一个链表是否是回文结构
	public boolean isPalindrome3(){
		if(this.head.next==null){
			return true;
		}
		Node n1 = this.head;
		Node n2 = this.head;
		while(n2.next!=null && n2.next.next!=null){
			n1=n1.next;
			n2=n2.next.next;
		}
		n2 = n1.next;
		n1.next = null;
		Node n3 = null;
		while(n2!=null){
			n3 = n2.next;
			n2.next = n1;
			n1 = n2;
			n2 = n3;
		}
		n3 = n1;
		n2 = this.head;
		boolean res = true;
		while(n1!=null &&n2!=null){
			if(n1.value!=n2.value){
				res = false;
				break;
			}
			n1 = n1.next;
			n2 = n2.next;
		}
		n1 = n3.next;
		n3.next = null;
		while(n1!=null){
			n2 = n1.next;
			n1.next = n3;
			n3 = n1;
			n1 = n2;
		}
		return res;
	}
	
	//单链表选择排序,包含头结点
	public void selectSortNode(){
		if(this.head.next==null){
			System.out.println("无需排序");
			return;
		}
		Node temp_first = this.head;
		while(temp_first.next!=null){
			Node temp_second = temp_first.next;
			while(temp_second !=null){
				if(temp_first.value>temp_second.value){
					int t = temp_second.value;
					temp_second.value = temp_first.value;
					temp_first.value = t;
				}
				temp_second = temp_second.next;
			}
			temp_first = temp_first.next;
		}
	}
	
	//单链表插入排序，包含头结点,思路是依次取出结点往前面排好序的链表里插入
	public void insertSortNode(){
		if(this.head.next==null){
			System.out.println("无需排序");
			return;
		}
		Node temp = this.head;
		while(temp.next!=null){
			//当temp.next结点大于temp时无需前插（temp是前面链表的最大值）
			if(temp.value<=temp.next.value){
				temp=temp.next;
			}
			//需要前插temp.next，取出temp.next,记录temp.next.next
			else{
				Node temp_1 = temp.next;
				Node temp_2 = temp.next.next;
				//断开链表（便于下一步temp.next插入合适位置循环操作）
				temp.next=null;
				//插入到链表最前面
				if(temp_1.value<=this.head.value){
					temp_1.next = this.head;
					this.head = temp_1;
				}
				//将temp.next插入到temp前面的有序链表中				
				else{
					Node temp_temp = this.head;
					while(temp_temp.next!=null){
						if(temp_1.value<=temp_temp.next.value){
							temp_1.next = temp_temp.next;
							temp_temp.next = temp_1;
							break;
						}
						temp_temp = temp_temp.next;
					}
				}
				//恢复链表，temp无需移动，因为temp.next已经更新，重新进入循环即可
				temp.next = temp_2;				
			}	
		}	
	}
	
	//单链表冒泡排序，包含头结点
	public void bubbleSort(){
		if(this.head.next==null){
			System.out.println("无需排序");
			return;
		}
		Node temp = this.head;
		Node tail = null;
		while(temp.next!=tail){
			while(temp.next!=tail){
				if(temp.value>temp.next.value){
					int t = temp.next.value;
					temp.next.value = temp.value;
					temp.value = t;
				}
				temp=temp.next;
			}
			tail = temp; //尾部终止点往前移动一位
			temp = this.head;//遍历起始结点重置为头结点
		}
	}
	
	//单链表快速排序，包含头结点，因为要倒序，所以快排其实不适合单链表
	//https://www.cnblogs.com/chilumanxi/p/5136146.html
	//原帖思路很好，只是有个错误（不能遍历到end结点）
	public void quickSort(Node begin,Node end){	
		if(begin == end){
			return;
		}
		Node temp = begin;
		Node small = begin;
		while(temp!=end){
			if(temp.next.value<begin.value){
				small = small.next;
				int t_1 = small.value;
				small.value = temp.next.value;
				temp.next.value = t_1;
			}
			temp = temp.next;			
		}
		int t_2 = begin.value;
		begin.value = small.value;
		small.value = t_2;
		quickSort(begin,small);
		quickSort(small.next,end);
	}
	
	//合并两个有序链表
	public Node mergeList(Node a,Node b){
		Node c = new Node(0);
		Node temp = c;
		while(a!=null && b !=null){
			if(a.value<=b.value){
				temp.next = a;
				a = a.next;
			}
			else{
				temp.next = b;
				b = b.next;
			}
			temp = temp.next;
		}
		while(a!=null){
			temp.next = a;
			a = a.next;
			temp = temp.next;
		}
		while(b!=null){
			temp.next = b;
			b = b.next;
			temp = temp.next;
		}
		return c.next;
	}
	
	//单链表归并排序
	public Node mergeSort(Node h){
		if (h == null || h.next == null) {
            return h;
        }
		Node middle = h;
        Node fast = h;
        while (fast.next != null && fast.next.next != null) {
            middle = middle.next;
            fast = fast.next.next;
        }
		Node sHalf = middle.next;
		middle.next = null;
		return mergeList(mergeSort(h),mergeSort(sHalf));	
	}
	
	//单链表反转
	public void reverse(){
		if(this.head.next==null){
			System.out.println("无需反转");
			return;
		}
		Node next = null;
		Node pre = null;
		while(this.head!=null){
			next = this.head.next;
			this.head.next = pre;
			pre = this.head;
			this.head = next;
		}
		this.head = pre;
	}
	
	//单链表部分反转
	public void reversePart(int from,int to){
		int length=0;
		Node node1 = this.head;
		Node fpre =null;
		Node tpos =null;
		while(node1!=null){
			length++;
			fpre = length==from-1?node1:fpre;
			tpos = length==to+1?node1:tpos;
			node1=node1.next;	
		}
		if(from >to || from <1 || to>length){
			return;
		}
		node1 = fpre==null?this.head:fpre.next;
		Node node2 = node1.next;
		node1.next =tpos;
		Node next = null;
		while(node2!=tpos){
			next = node2.next;
			node2.next = node1;
			node1=node2;
			node2=next;
		}
		if(fpre!=null){
			fpre.next = node1;
		}
		else{
			this.head = node1;
		}
	}
	
	//计算单链表的长度,包含头结点
	public int length(){
		int length=0;
		Node temp = this.head;
		while(temp!=null){
			length++;
			temp=temp.next;
		}	
		return length;
	}
	
	//获取倒数第k个结点
	public Node getLastNodeK(int k,int length){
		int i = 0;
		Node temp = this.head;
		if(k>length || k<1){
			System.out.println("k值无效");
			return null;//记得改为null
		}
		while(i++<length-k){
			temp = temp.next;
		}
		return temp;
	}
	
	//删除倒数第k个结点
	public void deleteLastNodeK(int k,int length){
		if(k>length || k<1){
			System.out.println("k值无效");
			return;
		}
		if(k==length){
			this.head = this.head.next;
		}
		else{
			int i = 1;
			Node temp = this.head;
			while(i++<length-k){
				temp = temp.next;
			}
			temp.next = temp.next.next;
		}
	}
	
	//删除第k个结点
	public void deleteNodeK(int k,int length){
		if(k>length || k<1){
			System.out.println("k值无效");
			return;
		}
		if(k==1){
			this.head = this.head.next;
		}
		else{
            int i = 1;			
			Node temp = this.head;
			while(++i<k){
				temp = temp.next;
			}
			temp.next = temp.next.next;		
		}
	}
	
	//删除链表中间节点
	public void deleteMiddleNode(){
		if(this.head.next==null){
			return;
		}
		if(this.head.next.next==null){
			this.head = this.head.next;
			return;
		}
		Node slow = this.head;
		Node fast = this.head.next;
		while(fast.next.next!=null && fast.next.next.next!=null){
			slow = slow.next;
			fast = fast.next.next;
		}
		slow.next = slow.next.next;
	}
	
	//判断链表是否有环
	public Node getLoopNode(){
		if(this.head.next ==null || this.head.next.next==null){
			return null;
		}
		Node n1 = this.head.next;
		Node n2 = this.head.next.next;
		while(n1!=n2){
			if(n2.next==null ||n2.next.next==null){
				return null;
			}
			n1 = n1.next;
			n2 = n2.next.next;
		}
		n2 = this.head;
		while(n1!=n2){
			n1 = n1.next;
			n2 = n2.next;
		}
		return n1;
	} 
	
	//删除单链表中值重复出现的结点
	public void removeRepeat(){
		if(this.head.next==null){
			return;
		}
		Node pre = null;
		Node next = null;
		Node cur = this.head;
		while(cur!=null){
			pre = cur;
			next = cur.next;
			while(next!=null){
				if(next.value==cur.value){
					pre.next = next.next;
				}
				else{
					pre = next;
				}
				next = next.next;
			}
			cur = cur.next;
		}		
	}
	
	//删除链表上值为n的结点
	public void removeValue(int n){
		while(this.head!=null){
			if(this.head.value!=n){
				break;
			}
			this.head = this.head.next;
		}
		Node pre = this.head;
		Node cur = this.head.next;
		while(cur!=null){
			if(cur.value==n){
				pre.next = cur.next;
			}
			else{
				pre = cur;
			}
			cur = cur.next;
		}
	}
	
	//向有序环形链表中插入新结点
	public Node insertNum(int num){
		Node node = new Node(num);
		if(head==null){
			node.next = node;
			return node;
		}
		Node pre = head;
		Node cur = head.next;
		while(cur!=head){
			if(pre.value<=num &&cur.value>=num){
				break;
			}
			pre = cur;
			cur = cur.next;
		}
		pre.next = node;
		node.next = cur;
		return head.value<num?head:node;
	}
	
	//判断两个无环链表是否相交
	public Node noLoop(Node head1,Node head2){
		if(head1==null || head2==null){
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n =0;
		while(cur1.next!=null){
			n++;
			cur1 = cur1.next;
		}
		while(cur2.next!=null){
			n--;
			cur2 = cur2.next;
		}
		if(cur1!=cur2){
			return null;
		}
		cur1 = n>0?head1:head2;
		cur2 = cur1==head1?head2:head1;
		n = Math.abs(n);
		while(n!=0){
			n--;
			cur1 = cur1.next;
		}
		while(cur1 != cur2){
			cur1 = cur1.next;
			cur1 = cur2.next;
		}
		return cur1;	
	}
	
	//遍历单链表，打印所有结点值
    public void print(){
        Node temp = this.head;
        while(temp != null){
            System.out.print(temp.value +",");
            temp = temp.next;
        }
        System.out.println();
    }
	
	public static void main(String[] args){
		SingleLinkedList myList = new SingleLinkedList(1);
		myList.addNode(myList.createNode(2));
		myList.addNode(myList.createNode(3));
		myList.addNode(myList.createNode(4));
		myList.addNode(myList.createNode(5));
        myList.addNode(myList.createNode(6));	
		myList.addNode(myList.createNode(7));
		myList.deleteMiddleNode();
		myList.print();
	}
	
}